package algorithm;

/**
 * 字节跳动在北京有N个工区，形成一个环状，Bytebus是往返在各个工区的通勤车，按工区的顺序行驶，其中第 i 个工区有汽油 gas[i] 升。
 * 你有一辆油箱容量无限的的Bytebus，从第 i 个工区开往第 i+1 个工区需要消耗汽油 cost[i] 升。
 * 你从其中的一个工区出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时工区的编号，否则返回 -1。
 * 输入:
 * gas = [1,2,3,4,5]
 * cost = [3,4,5,1,2]
 * 输出: 3
 *
 * @author Jake Weng
 */
public class ByteBusJake {

    public static int getStart(int[] gas, int[] cost) {
        if (gas == null || cost == null || cost.length < 2 || gas.length != cost.length) {
            return -1;
        }
        if (getSum(gas) < getSum(cost)) {
            return -1;
        }
        int start = -1;
        for (int i = 0; i < gas.length; i++) {
            if (gas[i] >= cost[i]) {
                start = i;
                if (isStartAvailable(gas, cost, start)) {
                    return start;
                }
            }
        }
        return start;
    }

    private static boolean isStartAvailable(int[] gas, int[] cost, int start) {
        int left = 0;
        for (int i = start; i < gas.length; i++) {
            left += gas[i];
            left -= cost[i];
            if (left < 0) {
                return false;
            }
        }
        for (int i = 0; i < start; i++) {
            left += gas[i];
            left -= cost[i];
            if (left < 0) {
                return false;
            }
        }
        return true;
    }

    private static int getSum(int[] arr) {
        int sum = 0;
        for (int element : arr) {
            sum += element;
        }
        return sum;
    }

}
